package main.java.indi.zyj.hot100;

import main.java.indi.zyj.hot100.base.ListNode;

import java.util.PriorityQueue;
import java.util.Queue;

public class _28_mergeKLists {

    public ListNode mergeKLists(ListNode[] lists) {

        ListNode ans = null;

        for (int i = 0; i < lists.length; ++i) {
            ans = merge(ans, lists[i]);
        }

        return ans;

    }

    public ListNode merge(ListNode p1, ListNode p2) {

        if (p1 == null || p2 == null) {
            return p1 == null ? p2 : p1;
        }

        ListNode head = new ListNode(-1);
        ListNode p = head;

        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }

        p.next = p1 != null ? p1 : p2;

        return head.next;

    }

    public ListNode mergeList2(ListNode[] lists) {
        if (lists.length == 0)
            return null;
        ListNode head = new ListNode(-1);
        ListNode p = head;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length,
                (a, b) -> a.val - b.val);
        for (ListNode list : lists) {
            if (list != null) {
                queue.offer(list);
            }
        }

        while (!queue.isEmpty()) {
            ListNode curNode = queue.poll();
            p.next = curNode;
            if(curNode.next != null){
                queue.offer(curNode.next);
            }
            p = p.next;
        }

        return head.next;

    }


    public ListNode mergeKLists1(ListNode[] lists) {
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for (ListNode node: lists) {
            if (node != null) {
                pq.offer(node);
            }
        }

        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (!pq.isEmpty()) {
            ListNode minNode = pq.poll();
            tail.next = minNode;
            tail = minNode;
            if (minNode.next != null) {
                pq.offer(minNode.next);
            }
        }

        return dummyHead.next;
    }



}
